꼭두각시 정렬
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
꼭두각시 정렬은 정렬 알고리즘의 하나로, 재귀 호출을 기반으로 한다. 배열의 처음 2/3, 마지막 2/3를 정렬하고, 다시 처음 2/3를 정렬하는 방식으로 구현된다. JavaScript, Haskell 등 다양한 프로그래밍 언어로 구현될 수 있다.
더 읽어볼만한 페이지
- 비교 정렬 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다. - 비교 정렬 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다. - 정렬 알고리즘 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다. - 정렬 알고리즘 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
| 꼭두각시 정렬 | |
|---|---|
| 알고리즘 개요 | |
| 종류 | 정렬 알고리즘 |
| 자료 구조 | 배열 |
| 시간 복잡도 | O(nlog 3/log 1.5) |
| 공간 복잡도 | O(n) |
| 최적화 여부 | 아니오 |
| 상세 정보 | |
| 시간 복잡도 (상세) | O(nlog 3 / log 1.5 ) = O(n2.7095...) |
 | |
2. 구현
꼭두각시 정렬 알고리즘은 재귀적인 방식으로 구현된다. 정렬 과정은 다음과 같은 단계로 이루어진다.
1. 정렬하고자 하는 배열(또는 배열의 일부)에서 첫 번째 요소와 마지막 요소를 비교한다. 만약 첫 번째 요소가 마지막 요소보다 크다면, 두 요소의 위치를 바꾼다.
2. 현재 처리 중인 배열(또는 배열의 일부)의 요소 개수가 3개 이상인지 확인한다.
3. 요소 개수가 3개 이상이라면, 배열의 길이를 3등분하여 크기 `t`를 계산한다. (정확히 나누어떨어지지 않으면 내림한다.)
4. 배열의 처음 2/3 (인덱스 `i`부터 `j-t`까지)에 대해 꼭두각시 정렬을 재귀적으로 호출한다.
5. 배열의 마지막 2/3 (인덱스 `i+t`부터 `j`까지)에 대해 꼭두각시 정렬을 재귀적으로 호출한다.
6. 배열의 처음 2/3 (인덱스 `i`부터 `j-t`까지)에 대해 꼭두각시 정렬을 다시 재귀적으로 호출한다. 이 마지막 단계를 통해 이전 단계에서 뒤쪽으로 밀려났을 수 있는 요소들이 올바른 위치를 찾아갈 수 있게 된다.
7. 요소 개수가 2개 이하이면 위의 재귀 호출 과정 없이 1번 단계만 수행하거나 아무 작업도 하지 않는다.
이러한 재귀적 호출을 통해 전체 배열이 정렬된다. 구체적인 구현 예시는 아래 하위 섹션에서 다양한 프로그래밍 언어로 확인할 수 있다.
2. 1. 의사 코드
자바스크립트와 유사한 의사 코드로 표현된 꼭두각시 정렬 알고리즘은 다음과 같다.function stoogesort(배열 L, i = 0, j = 길이(L)-1){
if L[i] > L[j] then // 만약 가장 왼쪽 요소가 가장 오른쪽 요소보다 크다면
swap(L[i],L[j]) // 두 요소를 바꾼다
if (j - i + 1) > 2 then // 만약 배열에 최소 3개의 요소가 있다면
t = floor((j - i + 1) / 3)
stoogesort(L, i, j-t) // 배열의 처음 2/3를 정렬한다
stoogesort(L, i+t, j) // 배열의 마지막 2/3를 정렬한다
stoogesort(L, i, j-t) // 배열의 처음 2/3를 다시 정렬한다
return L
}
2. 2. Haskell
함수형 프로그래밍 언어인 Haskell로 구현한 꼭두각시 정렬 알고리즘은 다음과 같다.- - 최선은 아니지만 위와 동일함
스투지 정렬 :: (Ord a) => [a] -> [a]
스투지정렬 [] = []
스투지정렬 src = innerStoogesort src 0 ((length src) - 1)
내부스투지정렬 :: (Ord a) => [a] -> Int -> Int -> [a]
내부스투지정렬 src i j
| (j - i + 1) > 2 = src''''
| otherwise = src'
where
src' = swap src i j -- 매 호출마다 필요
t = floor (fromIntegral (j - i + 1) / 3.0)
src'' = innerStoogesort src' i (j - t)
src''' = innerStoogesort src'' (i + t) j
src'''' = innerStoogesort src''' i (j - t)
swap :: (Ord a) => [a] -> Int -> Int -> [a]
swap src i j
| a > b = replaceAt (replaceAt src j a) i b
| otherwise = src
where
a = src !! i
b = src !! j
replaceAt :: [a] -> Int -> a -> [a]
replaceAt (x:xs) index value
| index == 0 = value : xs
| otherwise = x : replaceAt xs (index - 1) value
2. 3. JavaScript
wikitextfunction stoogesort(L, i = 0, j = L.length - 1) {
// 배열의 가장 왼쪽 요소가 가장 오른쪽 요소보다 크면 두 요소를 교환한다.
if (L[i] > L[j]) {
const temp = L[i];
L[i] = L[j];
L[j] = temp;
}
// 배열에 요소가 3개 이상 있으면
if (j - i + 1 > 2) {
const t = Math.floor((j - i + 1) / 3); // 내림 연산을 수행한다.
// 배열의 처음 2/3를 정렬한다.
stoogesort(L, i, j - t);
// 배열의 마지막 2/3를 정렬한다.
stoogesort(L, i + t, j);
// 배열의 처음 2/3를 다시 정렬한다.
stoogesort(L, i, j - t);
}
return L;
}
참조
[1]
웹사이트
CSE 373
https://courses.cs.w[...]
2020-09-14
[2]
문서
この2/3の操作は切り上げで行う。切り捨てにより行うと特定のデータで失敗する。例えば、数列{3,4,5,1,2}を切り捨てにより昇順にストゥージソートすると数列{1,2,4,3,5}が返され不正となる。
[3]
웹인용
CSE 373
https://courses.cs.w[...]
2020-09-14
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com